// Heapsort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <string>
#include <time.h>

#define WIN32_LEAN_AND_MEAN

#include <stdio.h>

// f has complexity = log n
void f(int* tab, int n)
{
	int i=n-1;
	// an O(log(n)) loop
	while(i>1)
	{
		int a;
		// an O(1) job
	 __asm 
	 { 
	  mov ecx, 1000000h 
	  mov eax, 0
loop0: 
	  inc eax
	  loop loop0
	  mov a, ebx
	 } 
		tab[i]=a;
		i /= 2;
	}
}

// g has complexity = n
void g(int* tab, int n)
{
	// an O(n) loop
	for (int i=0; i<n/2; i++)
	{
		int a;
		// an O(1) job
	 __asm 
	 { 
	  mov ecx, 100000h 
	  mov eax, 0
loop0: 
	  inc eax
	  loop loop0
	  mov a, ebx
	 } 
		tab[i]=a;
	}
}

// f_dot_g has complexity = n log n
void f_dot_g(int* tab, int n)
{
	int i=n-1;
	while(i>1)
	{
		int a;
		// an O(1) job
	 __asm 
	 { 
	  mov ecx, 1000000h 
	  mov eax, 0
loop0: 
	  inc eax
	  loop loop0
	  mov a, ebx
	 } 
		tab[i]=a;
		g(tab, n);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	int n = 1024;
	if (argc>1)
	{
		n = _ttoi(argv[1]);
	}
	int a=0;
	int i = 0, j=0;
	int *Array;
	Array = (int *)malloc(sizeof(int) * n);
	int tmp = 0;
	for( i=0; i<n; i++)
	{
		Array[i] = i;
	}
	srand ( time(NULL) );
	int target ;
	int found = -1;
	int loc = -1;
	std::string line;
	std::cout << "begin\r\n";
	std::getline(std::cin, line);
 
	f(Array,n);
	g(Array,n);

	std::cout << "end\r\n";
	//std::cout << "n=" << n << "\r\n";
	//std::cout << "target=" << target << "\r\n";
	//std::cout << "found=" << found << "\r\n";
	//std::cout << "loc=" << loc << "\r\n";
	free(Array);


	return 0;
}

